class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> arr; // 大小代表最长长度，值代表这个长度的子序列的最后一个值
        arr.push_back(nums[0]);
        for(int i = 1; i < nums.size(); ++i)
        {
            if(nums[i] > arr.back())
            {
                arr.push_back(nums[i]);
            }
            else // 二分找到要插入的位置
            {
                auto it = lower_bound(arr.begin(), arr.end(), nums[i]);
                if(it != arr.end()) // 第一个大于等于的位置
                    *it = nums[i];
            }
        }
        return arr.size();
    }
};
/*class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), ret = 1;
        vector<int> dp(n, 1); // dp[i]表示以i为结尾的最长递增子序列长度
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i], dp[j] + 1);
            }
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};
*/